home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-01
/
bfsorts.zip
/
SSORT.C
< prev
next >
Wrap
C/C++ Source or Header
|
1990-12-26
|
3KB
|
92 lines
/***********************************************************************/
/* SORT(): Non-Recursive Shell's Sort function. */
/* See the function declaration for calling information. */
/* Function is by Bruce Feist; please contact me on CompuServe with */
/* a message on BPROGB, MACDEV, or EASYPLEX if you have any */
/* questions or problems. */
/* You can also reach me at the Enlightened Board, at (703) 370-9528, */
/* N/8/1 */
/* Feel free to make use of this code in your own programs. */
/***********************************************************************/
/* Shell's sort. Not bad for intermediate sizes. */
/* Uses increment sequence h(n+1) = 3*h(n) + 1, */
/* as suggested by Knuth. */
#include <alloc.h>
#include <mem.h>
#include <stddef.h>
#include <stdio.h>
#include "sort.h"
#define VERBOSE (0)
static char *base;
static double *dbase;
static int nelem, width;
static int (*compare) (void *, void *);
static int get_increment (int n_elements);
static char *temp_record;
int
ssort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
register unsigned int increment;
long offset;
register unsigned int equiv_class;
base = pbase;
dbase = pbase; /* for debugging only */
nelem = pnelem;
width = pwidth;
compare = pcompare;
temp_record = malloc (width);
if (temp_record == NULL)
return S_NOMEM;
for (increment = get_increment (nelem);
increment > 0;
increment /= 3)
{
for (equiv_class = increment;
equiv_class < nelem;
equiv_class++)
{
memcpy (temp_record, base + equiv_class * width, width);
for (offset = equiv_class - increment;
offset >= 0 &&
#pragma warn -sig
(*compare) (temp_record, base + offset * width) < 0;
#pragma warn .sig
offset -= increment)
{
#pragma warn -sig
memcpy (base + (increment + offset) * width,
base + offset * width,
#pragma warn .sig
width);
} /* end for offset */
#pragma warn -sig
memcpy (base + (offset + increment) * width, temp_record, width);
#pragma warn .sig
} /* end for equiv_class */
} /* end for increment */
return S_OK;
} /* end ssort */
int
get_increment (int n_elements)
{
register int inc;
for (inc = 1;
inc < n_elements;
inc = 3 * inc + 1)
;
return inc > 17 ? inc/9 : 1;
} /* end get_increment */